{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Increment Submatrices by One"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #matrix #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #矩阵 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: rangeAddQueries"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #子矩阵元素加 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个正整数 <code>n</code> ，表示最初有一个 <code>n x n</code> 、下标从 <strong>0</strong> 开始的整数矩阵 <code>mat</code> ，矩阵中填满了 0 。</p>\n",
    "\n",
    "<p>另给你一个二维整数数组 <code>query</code> 。针对每个查询 <code>query[i] = [row1<sub>i</sub>, col1<sub>i</sub>, row2<sub>i</sub>, col2<sub>i</sub>]</code> ，请你执行下述操作：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>找出 <strong>左上角</strong> 为 <code>(row1<sub>i</sub>, col1<sub>i</sub>)</code> 且 <strong>右下角</strong> 为 <code>(row2<sub>i</sub>, col2<sub>i</sub>)</code> 的子矩阵，将子矩阵中的 <strong>每个元素</strong> 加 <code>1</code> 。也就是给所有满足 <code>row1<sub>i</sub> &lt;= x &lt;= row2<sub>i</sub></code> 和 <code>col1<sub>i</sub> &lt;= y &lt;= col2<sub>i</sub></code> 的 <code>mat[x][y]</code> 加 <code>1</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回执行完所有操作后得到的矩阵 <code>mat</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/11/24/p2example11.png\" style=\"width: 531px; height: 121px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 3, queries = [[1,1,2,2],[0,0,1,1]]\n",
    "<strong>输出：</strong>[[1,1,0],[1,2,1],[0,1,1]]\n",
    "<strong>解释：</strong>上图所展示的分别是：初始矩阵、执行完第一个操作后的矩阵、执行完第二个操作后的矩阵。\n",
    "- 第一个操作：将左上角为 (1, 1) 且右下角为 (2, 2) 的子矩阵中的每个元素加 1 。 \n",
    "- 第二个操作：将左上角为 (0, 0) 且右下角为 (1, 1) 的子矩阵中的每个元素加 1 。 \n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/11/24/p2example22.png\" style=\"width: 261px; height: 82px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 2, queries = [[0,0,1,1]]\n",
    "<strong>输出：</strong>[[1,1],[1,1]]\n",
    "<strong>解释：</strong>上图所展示的分别是：初始矩阵、执行完第一个操作后的矩阵。 \n",
    "- 第一个操作：将矩阵中的每个元素加 1 。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 500</code></li>\n",
    "\t<li><code>1 &lt;= queries.length &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>0 &lt;= row1<sub>i</sub> &lt;= row2<sub>i</sub> &lt; n</code></li>\n",
    "\t<li><code>0 &lt;= col1<sub>i</sub> &lt;= col2<sub>i</sub> &lt; n</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [increment-submatrices-by-one](https://leetcode.cn/problems/increment-submatrices-by-one/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [increment-submatrices-by-one](https://leetcode.cn/problems/increment-submatrices-by-one/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['3\\n[[1,1,2,2],[0,0,1,1]]', '2\\n[[0,0,1,1]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:\n",
    "        ans = [[0] * (n + 1) for _ in range(n + 1)]\n",
    "        # 二维差分\n",
    "        for r1, c1, r2, c2 in queries:\n",
    "            ans[r1][c1] += 1\n",
    "            ans[r2 + 1][c2 + 1] += 1\n",
    "            ans[r1][c2 + 1] -= 1\n",
    "            ans[r2 + 1][c1] -= 1\n",
    "        ans.pop()\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(n + 1):\n",
    "                if i > 0:\n",
    "                    ans[i][j] += ans[i - 1][j]\n",
    "                    if j > 0:\n",
    "                        ans[i][j] -= ans[i - 1][j - 1]\n",
    "                if j > 0:\n",
    "                    ans[i][j] += ans[i][j - 1]\n",
    "                    \n",
    "        \n",
    "        for l in ans:\n",
    "            l.pop()\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:\n",
    "        # 二维差分模板\n",
    "        diff = [[0] * (n + 2) for _ in range(n + 2)]\n",
    "        for r1, c1, r2, c2 in queries:\n",
    "            diff[r1 + 1][c1 + 1] += 1\n",
    "            diff[r1 + 1][c2 + 2] -= 1\n",
    "            diff[r2 + 2][c1 + 1] -= 1\n",
    "            diff[r2 + 2][c2 + 2] += 1\n",
    "\n",
    "        # 用二维前缀和复原（原地修改）\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                diff[i][j] += diff[i][j - 1] + diff[i - 1][j] - diff[i - 1][j - 1]\n",
    "        # 保留中间 n*n 的部分，即为答案\n",
    "        diff = diff[1:-1]\n",
    "        for i, row in enumerate(diff):\n",
    "            diff[i] = row[1:-1]\n",
    "        return diff\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:\n",
    "        # 暴力会超时\n",
    "        # ans = [[0] * n for _ in range(n)]\n",
    "        # for query in queries:\n",
    "        #     sx, sy, ex, ey = query\n",
    "        #     for i in range(sx, ex+1):\n",
    "        #         for j in range(sy, ey+1):\n",
    "        #             ans[i][j] += 1\n",
    "        # return ans\n",
    "\n",
    "        # 方法一： 对每一行做差分\n",
    "        ans = [[0] * n for _ in range(n)]\n",
    "        for r1, c1, r2, c2 in queries:\n",
    "            for r in range(r1, r2+1):\n",
    "                ans[r][c1] += 1\n",
    "                if c2 + 1 < n:\n",
    "                    ans[r][c2 + 1] -= 1\n",
    "        \n",
    "        # 差分的前缀和是原数组 (差分相当于导数，前缀和相当于积分)\n",
    "        for row in ans:\n",
    "            for j in range(1, n):\n",
    "                row[j] += row[j-1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:\n",
    "        # 二维差分模板\n",
    "        diff = [[0] * (n + 2) for _ in range(n + 2)]\n",
    "        for r1, c1, r2, c2 in queries:\n",
    "            diff[r1 + 1][c1 + 1] += 1\n",
    "            diff[r1 + 1][c2 + 2] -= 1\n",
    "            diff[r2 + 2][c1 + 1] -= 1\n",
    "            diff[r2 + 2][c2 + 2] += 1\n",
    "\n",
    "        # 用二维前缀和复原（原地修改）\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                diff[i][j] += diff[i][j - 1] + diff[i - 1][j] - diff[i - 1][j - 1]\n",
    "        # 保留中间 n*n 的部分，即为答案\n",
    "        diff = diff[1:-1]\n",
    "        for i, row in enumerate(diff):\n",
    "            diff[i] = row[1:-1]\n",
    "        return diff\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:\n",
    "        ans = [[0] * (n + 2) for _ in range(n + 2)]\n",
    "        # 二维差分\n",
    "        for r1, c1, r2, c2 in queries:\n",
    "            ans[r1][c1] += 1\n",
    "            ans[r1][c2 + 1] -= 1\n",
    "            ans[r2 + 1][c1] -= 1\n",
    "            ans[r2 + 1][c2 + 1] += 1\n",
    "\n",
    "        for i in range(n):\n",
    "            i2 = i - 1\n",
    "            for j in range(n):\n",
    "                ans[i][j] += ans[i][j - 1] + ans[i2][j] - ans[i2][j - 1]\n",
    "                    \n",
    "        ans.pop()\n",
    "        ans.pop()\n",
    "        for l in ans:\n",
    "            l.pop()\n",
    "            l.pop()\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:\n",
    "        # 二维差分模板\n",
    "        diff = [[0] * (n + 2) for _ in range(n + 2)]\n",
    "        for r1, c1, r2, c2 in queries:\n",
    "            diff[r1 + 1][c1 + 1] += 1\n",
    "            diff[r1 + 1][c2 + 2] -= 1\n",
    "            diff[r2 + 2][c1 + 1] -= 1\n",
    "            diff[r2 + 2][c2 + 2] += 1\n",
    "\n",
    "        # 用二维前缀和复原（原地修改）\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                diff[i][j] += diff[i][j - 1] + diff[i - 1][j] - diff[i - 1][j - 1]\n",
    "        # 保留中间 n*n 的部分，即为答案\n",
    "        diff = diff[1:-1]\n",
    "        for i, row in enumerate(diff):\n",
    "            diff[i] = row[1:-1]\n",
    "        return diff\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:\n",
    "        diff = [[0]*n for _ in range(n)]\n",
    "        for r1,c1,r2,c2 in queries:\n",
    "            for i in range(r1,r2+1):\n",
    "                diff[i][c1] += 1\n",
    "                if(c2+1 < n):\n",
    "                    diff[i][c2+1] -= 1\n",
    "        for i in range(n):\n",
    "            for j in range(1,n):\n",
    "                diff[i][j] += diff[i][j-1]\n",
    "        return diff"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:\n",
    "        ans = [[0] * (n + 1) for _ in range(n)]\n",
    "        # 差分\n",
    "        for r1, c1, r2, c2 in queries:\n",
    "            for r in range(r1, r2+1):\n",
    "                ans[r][c1] += 1\n",
    "                ans[r][c2 + 1] -= 1\n",
    "        cnt = 0\n",
    "        for i in range(n):\n",
    "            for j in range(n + 1):\n",
    "                cnt += ans[i][j]\n",
    "                ans[i][j] = cnt\n",
    "            ans[i].pop()\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:\n",
    "        diff = [[0]*n for _ in range(n)]\n",
    "        for r1,c1,r2,c2 in queries:\n",
    "            for i in range(r1,r2+1):\n",
    "                diff[i][c1] += 1\n",
    "                if(c2+1 < n):\n",
    "                    diff[i][c2+1] -= 1\n",
    "        for i in range(n):\n",
    "            for j in range(1,n):\n",
    "                diff[i][j] += diff[i][j-1]\n",
    "        return diff"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:\n",
    "        res = [[0] * n for _ in range(n)]\n",
    "        for row1, col1, row2, col2 in queries:\n",
    "            for r in range(row1, row2+1):\n",
    "                res[r][col1] += 1\n",
    "                if col2 + 1 < n:\n",
    "                    res[r][col2+1] -= 1\n",
    "        for r in range(n):\n",
    "            for c in range(1, n):\n",
    "                res[r][c] += res[r][c-1]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:\n",
    "        # 二维差分模板\n",
    "        diff = [[0] * (n + 2) for _ in range(n + 2)]\n",
    "        for r1, c1, r2, c2 in queries:\n",
    "            diff[r1 + 1][c1 + 1] += 1\n",
    "            diff[r1 + 1][c2 + 2] -= 1\n",
    "            diff[r2 + 2][c1 + 1] -= 1\n",
    "            diff[r2 + 2][c2 + 2] += 1\n",
    "\n",
    "        # 用二维前缀和复原（原地修改）\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                diff[i][j] += diff[i][j - 1] + diff[i - 1][j] - diff[i - 1][j - 1]\n",
    "        # 保留中间 n*n 的部分，即为答案\n",
    "        diff = diff[1:-1]\n",
    "        for i, row in enumerate(diff):\n",
    "            diff[i] = row[1:-1]\n",
    "        return diff\n",
    "\n",
    "# 作者：灵茶山艾府\n",
    "# 链接：https://leetcode.cn/problems/increment-submatrices-by-one/solutions/2062756/er-wei-chai-fen-by-endlesscheng-mh0h/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:\n",
    "        # 二维差分模板\n",
    "        diff = [[0] * (n + 2) for _ in range(n + 2)]\n",
    "        for r1, c1, r2, c2 in queries:\n",
    "            diff[r1 + 1][c1 + 1] += 1\n",
    "            diff[r1 + 1][c2 + 2] -= 1\n",
    "            diff[r2 + 2][c1 + 1] -= 1\n",
    "            diff[r2 + 2][c2 + 2] += 1\n",
    "\n",
    "        # 用二维前缀和复原（原地修改）\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                diff[i][j] += diff[i][j - 1] + diff[i - 1][j] - diff[i - 1][j - 1]\n",
    "        # 保留中间 n*n 的部分，即为答案\n",
    "        diff = diff[1:-1]\n",
    "        for i, row in enumerate(diff):\n",
    "            diff[i] = row[1:-1]\n",
    "        return diff"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:\n",
    "        diff = [[0] * n for _ in range(n)]\n",
    "        for r1, c1, r2, c2 in queries:\n",
    "            diff[r1][c1] += 1\n",
    "            if c2 + 1 < n:\n",
    "                diff[r1][c2 + 1] -= 1\n",
    "            if r2 + 1 < n:\n",
    "                diff[r2 + 1][c1] -= 1\n",
    "            if r2 + 1 < n and c2 + 1 < n:\n",
    "                diff[r2 + 1][c2 + 1] += 1\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(1, n):\n",
    "                diff[i][j] += diff[i][j - 1]\n",
    "        for j in range(n):\n",
    "            for i in range(1, n):\n",
    "                diff[i][j] += diff[i - 1][j]\n",
    "        \n",
    "        return diff"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:\n",
    "        ans = [[0] * (n + 2) for _ in range(n + 2)]\n",
    "        # 二维差分\n",
    "        for r1, c1, r2, c2 in queries:\n",
    "            ans[r1][c1] += 1\n",
    "            ans[r2 + 1][c2 + 1] += 1\n",
    "            ans[r1][c2 + 1] -= 1\n",
    "            ans[r2 + 1][c1] -= 1\n",
    "\n",
    "        for i in range(n):\n",
    "            i2 = i - 1\n",
    "            for j in range(n):\n",
    "                ans[i][j] += ans[i][j - 1] + ans[i2][j] - ans[i2][j - 1]\n",
    "                    \n",
    "        ans.pop()\n",
    "        ans.pop()\n",
    "        for l in ans:\n",
    "            l.pop()\n",
    "            l.pop()\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:\n",
    "        # 二维差分模板\n",
    "        diff = [[0] * (n + 2) for _ in range(n + 2)]\n",
    "        for r1, c1, r2, c2 in queries:\n",
    "            diff[r1 + 1][c1 + 1] += 1\n",
    "            diff[r1 + 1][c2 + 2] -= 1\n",
    "            diff[r2 + 2][c1 + 1] -= 1\n",
    "            diff[r2 + 2][c2 + 2] += 1\n",
    "\n",
    "        # 用二维前缀和复原（原地修改）\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                diff[i][j] += diff[i][j - 1] + diff[i - 1][j] - diff[i - 1][j - 1]\n",
    "        # 保留中间 n*n 的部分，即为答案\n",
    "        diff = diff[1:-1]\n",
    "        for i, row in enumerate(diff):\n",
    "            diff[i] = row[1:-1]\n",
    "        return diff\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:\n",
    "        diff = [[0]*n for _ in range(n)]\n",
    "        for r1,c1,r2,c2 in queries:\n",
    "            for i in range(r1,r2+1):\n",
    "                diff[i][c1] += 1\n",
    "                if(c2+1 < n):\n",
    "                    diff[i][c2+1] -= 1\n",
    "        for i in range(n):\n",
    "            for j in range(1,n):\n",
    "                diff[i][j] += diff[i][j-1]\n",
    "        return diff"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:\n",
    "#         mat = [[0 for _ in range(n)] for _ in range(n)]\n",
    "#         for i in range(len(queries)):\n",
    "#             row_1 = queries[i][0]\n",
    "#             col_1 = queries[i][1]\n",
    "#             row_2 = queries[i][2]\n",
    "#             col_2 = queries[i][3]\n",
    "#             for x in range(row_1,row_2+1):\n",
    "#                 for y in range(col_1,col_2+1):\n",
    "#                     mat[x][y] += 1\n",
    "#         return mat \n",
    "\n",
    "class Solution:\n",
    "    def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:\n",
    "        # 二维差分模板\n",
    "        diff = [[0] * (n + 2) for _ in range(n + 2)]\n",
    "        for r1, c1, r2, c2 in queries:\n",
    "            diff[r1 + 1][c1 + 1] += 1\n",
    "            diff[r1 + 1][c2 + 2] -= 1\n",
    "            diff[r2 + 2][c1 + 1] -= 1\n",
    "            diff[r2 + 2][c2 + 2] += 1\n",
    "\n",
    "        # 用二维前缀和复原（原地修改）\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                diff[i][j] += diff[i][j - 1] + diff[i - 1][j] - diff[i - 1][j - 1]\n",
    "        # 保留中间 n*n 的部分，即为答案\n",
    "        diff = diff[1:-1]\n",
    "        for i, row in enumerate(diff):\n",
    "            diff[i] = row[1:-1]\n",
    "        return diff\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:\n",
    "        # 二维差分模板\n",
    "        diff = [[0] * (n + 2) for _ in range(n + 2)]\n",
    "        for r1, c1, r2, c2 in queries:\n",
    "            diff[r1 + 1][c1 + 1] += 1\n",
    "            diff[r1 + 1][c2 + 2] -= 1\n",
    "            diff[r2 + 2][c1 + 1] -= 1\n",
    "            diff[r2 + 2][c2 + 2] += 1\n",
    "\n",
    "        # 用二维前缀和复原（原地修改）\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                diff[i][j] += diff[i][j - 1] + diff[i - 1][j] - diff[i - 1][j - 1]\n",
    "        # 保留中间 n*n 的部分，即为答案\n",
    "        diff = diff[1:-1]\n",
    "        for i, row in enumerate(diff):\n",
    "            diff[i] = row[1:-1]\n",
    "        return diff\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:\n",
    "        # 二维差分模板\n",
    "        diff = [[0] * (n + 2) for _ in range(n + 2)]\n",
    "        for r1, c1, r2, c2 in queries:\n",
    "            diff[r1 + 1][c1 + 1] += 1\n",
    "            diff[r1 + 1][c2 + 2] -= 1\n",
    "            diff[r2 + 2][c1 + 1] -= 1\n",
    "            diff[r2 + 2][c2 + 2] += 1\n",
    "\n",
    "        # 用二维前缀和复原（原地修改）\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                diff[i][j] += diff[i][j - 1] + diff[i - 1][j] - diff[i - 1][j - 1]\n",
    "        # 保留中间 n*n 的部分，即为答案\n",
    "        diff = diff[1:-1]\n",
    "        for i, row in enumerate(diff):\n",
    "            diff[i] = row[1:-1]\n",
    "        return diff\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:\n",
    "        ans = [[0] * (n + 2) for _ in range(n + 2)]\n",
    "        # 二维差分\n",
    "        for r1, c1, r2, c2 in queries:\n",
    "            ans[r1][c1] += 1\n",
    "            ans[r2 + 1][c2 + 1] += 1\n",
    "            ans[r1][c2 + 1] -= 1\n",
    "            ans[r2 + 1][c1] -= 1\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                ans[i][j] += ans[i][j - 1] + ans[i - 1][j] - ans[i - 1][j - 1]\n",
    "                    \n",
    "        ans.pop()\n",
    "        ans.pop()\n",
    "        for l in ans:\n",
    "            l.pop()\n",
    "            l.pop()\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:\n",
    "        res = [[0] * n for _ in range(n)]\n",
    "        for row1, col1, row2, col2 in queries:\n",
    "            for i in range(row1, row2 + 1):\n",
    "                res[i][col1] += 1\n",
    "                if col2 + 1 < n:\n",
    "                    res[i][col2+1] -= 1\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(1, n):\n",
    "                res[i][j] += res[i][j-1]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:\n",
    "        ans = [[0] * (n + 2) for _ in range(n + 2)]\n",
    "        # 二维差分\n",
    "        for r1, c1, r2, c2 in queries:\n",
    "            ans[r1][c1] += 1\n",
    "            ans[r1][c2 + 1] -= 1\n",
    "            ans[r2 + 1][c1] -= 1\n",
    "            ans[r2 + 1][c2 + 1] += 1\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                ans[i][j] += ans[i][j - 1] + ans[i - 1][j] - ans[i - 1][j - 1]\n",
    "                    \n",
    "        ans.pop()\n",
    "        ans.pop()\n",
    "        for l in ans:\n",
    "            l.pop()\n",
    "            l.pop()\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:\n",
    "        # 二维差分模板\n",
    "        diff = [[0] * (n + 2) for _ in range(n + 2)]\n",
    "        for r1, c1, r2, c2 in queries:\n",
    "            diff[r1 + 1][c1 + 1] += 1\n",
    "            diff[r1 + 1][c2 + 2] -= 1\n",
    "            diff[r2 + 2][c1 + 1] -= 1\n",
    "            diff[r2 + 2][c2 + 2] += 1\n",
    "\n",
    "        # 用二维前缀和复原（原地修改）\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                diff[i][j] += diff[i][j - 1] + diff[i - 1][j] - diff[i - 1][j - 1]\n",
    "        # 保留中间 n*n 的部分，即为答案\n",
    "        diff = diff[1:-1]\n",
    "        for i, row in enumerate(diff):\n",
    "            diff[i] = row[1:-1]\n",
    "        return diff\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:\n",
    "        # 二维差分模板\n",
    "        diff = [[0] * (n + 2) for _ in range(n + 2)]\n",
    "        # 二维变化量\n",
    "        for r1, c1, r2, c2 in queries:\n",
    "            diff[r1 + 1][c1 + 1] += 1\n",
    "            diff[r1 + 1][c2 + 2] -= 1\n",
    "            diff[r2 + 2][c1 + 1] -= 1\n",
    "            diff[r2 + 2][c2 + 2] += 1\n",
    "            # print(diff[1:-1])\n",
    "            # print(diff)\n",
    "\n",
    "        # 用二维前缀和复原（原地修改）\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                diff[i][j] += diff[i][j - 1] + diff[i - 1][j] - diff[i - 1][j - 1]\n",
    "        # print(diff[1:-1])\n",
    "        # 保留中间 n*n 的部分，即为答案\n",
    "        diff = diff[1:-1]\n",
    "        for i, row in enumerate(diff):\n",
    "            diff[i] = row[1:-1]\n",
    "        return diff\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:\n",
    "        matrix = [[0] * n for _ in range(n)]\n",
    "        for r1, c1, r2, c2 in queries:\n",
    "            for i in range(r1, r2 + 1):\n",
    "                matrix[i][c1] += 1\n",
    "                if c2 + 1 < n:\n",
    "                    matrix[i][c2 + 1] -= 1\n",
    "        for i in range(n):\n",
    "            for j in range(1, n):\n",
    "                matrix[i][j] += matrix[i][j - 1]\n",
    "        return matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:\n",
    "        ans = [[0] * (n + 1) for _ in range(n + 1)]\n",
    "        # 二维差分\n",
    "        for r1, c1, r2, c2 in queries:\n",
    "            ans[r1][c1] += 1\n",
    "            ans[r2 + 1][c2 + 1] += 1\n",
    "            ans[r1][c2 + 1] -= 1\n",
    "            ans[r2 + 1][c1] -= 1\n",
    "        ans.pop()\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(n + 1):\n",
    "                if i > 0:\n",
    "                    ans[i][j] += ans[i - 1][j]\n",
    "                if j > 0:\n",
    "                    ans[i][j] += ans[i][j - 1]\n",
    "                if i > 0 and j > 0:\n",
    "                    ans[i][j] -= ans[i - 1][j - 1]\n",
    "        \n",
    "        for l in ans:\n",
    "            l.pop()\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:\n",
    "        # 二维差分模板\n",
    "        diff = [[0] * (n + 2) for _ in range(n + 2)]\n",
    "        for r1, c1, r2, c2 in queries:\n",
    "            diff[r1 + 1][c1 + 1] += 1\n",
    "            diff[r1 + 1][c2 + 2] -= 1\n",
    "            diff[r2 + 2][c1 + 1] -= 1\n",
    "            diff[r2 + 2][c2 + 2] += 1\n",
    "\n",
    "        # 用二维前缀和复原（原地修改）\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                diff[i][j] += diff[i][j - 1] + diff[i - 1][j] - diff[i - 1][j - 1]\n",
    "        # 保留中间 n*n 的部分，即为答案\n",
    "        diff = diff[1:-1]\n",
    "        for i, row in enumerate(diff):\n",
    "            diff[i] = row[1:-1]\n",
    "        return diff\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:\n",
    "        diff = [[0]*(n+2) for _ in range(n+2)]\n",
    "        for r1,c1,r2,c2 in queries:\n",
    "            diff[r1+1][c1+1] += 1\n",
    "            diff[r1+1][c2+2] -= 1\n",
    "            diff[r2+2][c1+1] -= 1\n",
    "            diff[r2+2][c2+2] += 1\n",
    "\n",
    "        # 用二维前缀和复原\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(1,n+1):\n",
    "                diff[i][j] += diff[i][j-1]+diff[i-1][j]-diff[i-1][j-1]\n",
    "\n",
    "        # 保留中间 n*n 的部分，即为答案\n",
    "        diff = diff[1:-1]\n",
    "        for i,row in enumerate(diff):\n",
    "            diff[i] = row[1:-1]\n",
    "        return diff"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:\n",
    "        diff = [[0] * (n + 2) for _ in range(n + 2)]\n",
    "        for r1, c1, r2, c2 in queries:\n",
    "            diff[r1 + 1][c1 + 1] += 1\n",
    "            diff[r1 + 1][c2 + 2] -= 1\n",
    "            diff[r2 + 2][c1 + 1] -= 1\n",
    "            diff[r2 + 2][c2 + 2] += 1\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                diff[i][j] += diff[i][j - 1] + diff[i - 1][j] - diff[i - 1][j - 1]\n",
    "        diff = diff[1:-1]\n",
    "        for i, row in enumerate(diff):\n",
    "            diff[i] = row[1:-1]\n",
    "        return diff                                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:\n",
    "        ans = [[0] * n for _ in range(n)]\n",
    "        for query in queries:\n",
    "            ans[query[0]][query[1]] += 1\n",
    "            if query[2] < n - 1:\n",
    "                ans[query[2] + 1][query[1]] -= 1\n",
    "            if query[3] < n - 1:\n",
    "                ans[query[0]][query[3] + 1] -= 1\n",
    "            if query[2] < n - 1 and query[3] < n - 1:\n",
    "                ans[query[2] + 1][query[3] + 1] += 1\n",
    "        # print(ans)\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                a = ans[i - 1][j] if i > 0 else 0\n",
    "                b = ans[i][j - 1] if j > 0 else 0\n",
    "                c = ans[i - 1][j - 1] if i > 0 and j > 0 else 0\n",
    "                ans[i][j] += a + b - c\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:\n",
    "        # 二维差分模板\n",
    "        diff = [[0] * (n + 2) for _ in range(n + 2)]\n",
    "        for r1, c1, r2, c2 in queries:\n",
    "            diff[r1 + 1][c1 + 1] += 1\n",
    "            diff[r1 + 1][c2 + 2] -= 1\n",
    "            diff[r2 + 2][c1 + 1] -= 1\n",
    "            diff[r2 + 2][c2 + 2] += 1\n",
    "\n",
    "        # 用二维前缀和复原（原地修改）\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                diff[i][j] += diff[i][j - 1] + diff[i - 1][j] - diff[i - 1][j - 1]\n",
    "        # 保留中间 n*n 的部分，即为答案\n",
    "        diff = diff[1:-1]\n",
    "        for i, row in enumerate(diff):\n",
    "            diff[i] = row[1:-1]\n",
    "        return diff\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:\n",
    "        # 二维差分模板\n",
    "        diff = [[0] * (n + 2) for _ in range(n + 2)]\n",
    "        for r1, c1, r2, c2 in queries:\n",
    "            diff[r1 + 1][c1 + 1] += 1\n",
    "            diff[r1 + 1][c2 + 2] -= 1\n",
    "            diff[r2 + 2][c1 + 1] -= 1\n",
    "            diff[r2 + 2][c2 + 2] += 1\n",
    "\n",
    "        # 用二维前缀和复原（原地修改）\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                diff[i][j] += diff[i][j - 1] + diff[i - 1][j] - diff[i - 1][j - 1]\n",
    "        # 保留中间 n*n 的部分，即为答案\n",
    "        diff = diff[1:-1]\n",
    "        for i, row in enumerate(diff):\n",
    "            diff[i] = row[1:-1]\n",
    "        return diff\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:\n",
    "        diff = [[0]*(n + 2) for _ in range(n + 2)]\n",
    "        for x1,y1,x2,y2 in queries:\n",
    "            diff[x1 + 1][y1 + 1] += 1\n",
    "            diff[x2 + 2][y1 + 1] -= 1\n",
    "            diff[x1 + 1][y2 + 2] -= 1\n",
    "            diff[x2 + 2][y2 + 2] += 1\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                diff[i + 1][j + 1] += diff[i][j + 1] + diff[i + 1][j] - diff[i][j]\n",
    "        \n",
    "        diff = diff[1:-1]\n",
    "        for i,row in enumerate(diff):\n",
    "            diff[i] = row[1:-1]\n",
    "        return diff"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:\n",
    "        diff = [[0] * (n+2) for i in range(n+2)]\n",
    "        for x1, y1, x2, y2 in queries:\n",
    "            diff[x1+1][y1+1] += 1\n",
    "            diff[x2+2][y1+1] -= 1\n",
    "            diff[x1+1][y2+2] -= 1\n",
    "            diff[x2+2][y2+2] += 1\n",
    "        \n",
    "        # 原地求前缀和\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(1, n+1):\n",
    "                diff[i][j] = diff[i-1][j] + diff[i][j-1] - diff[i-1][j-1] + diff[i][j]\n",
    "        \n",
    "        diff = diff[1:-1]\n",
    "        for i, row in enumerate(diff):\n",
    "            diff[i] = row[1:-1]\n",
    "        \n",
    "        return diff"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:\n",
    "        diff = [[0] * (n+1) for i in range(n+1)]\n",
    "        for r1, c1, r2, c2 in queries:\n",
    "            diff[r1][c1] += 1\n",
    "            diff[r2+1][c1] -= 1\n",
    "            diff[r1][c2+1] -= 1\n",
    "            diff[r2+1][c2+1] += 1\n",
    "\n",
    "        # ans = [[0] * n for i in range(n)]\n",
    "        # ans[0][0] = diff[0][0]\n",
    "        # for k in range(1,n):\n",
    "        #     ans[0][k] = ans[0][k-1] + diff[0][k]\n",
    "        #     ans[k][0] = ans[k-1][0] + diff[k][0]\n",
    "        \n",
    "        # for i in range(1, n):\n",
    "        #     for j in range(1,n):\n",
    "        #         ans[i][j] = ans[i-1][j] + ans[i][j-1] - ans[i-1][j-1] + diff[i][j]\n",
    "\n",
    "        # return ans\n",
    "\n",
    "\n",
    "        for k in range(1, n):\n",
    "            diff[0][k] += diff[0][k-1]\n",
    "            diff[k][0] += diff[k-1][0]\n",
    "        \n",
    "        diff[0] = diff[0][:-1]\n",
    "        for i in range(1, n):\n",
    "            for j in range(1, n):\n",
    "                diff[i][j] += diff[i-1][j] + diff[i][j-1] - diff[i-1][j-1]\n",
    "\n",
    "            diff[i] = diff[i][:-1]\n",
    "        \n",
    "        return diff[:-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:\n",
    "        class diff2:\n",
    "            def __init__(self,m,n):\n",
    "                self.m=m\n",
    "                self.n=n\n",
    "                self.diff=[[0] * (n + 2) for _ in range(m + 2)]\n",
    "            def add(self,r1,c1,r2,c2,c):\n",
    "                diff=self.diff\n",
    "                diff[r1 + 1][c1 + 1] += c\n",
    "                diff[r1 + 1][c2 + 2] -= c\n",
    "                diff[r2 + 2][c1 + 1] -= c\n",
    "                diff[r2 + 2][c2 + 2] += c    \n",
    "            def get(self):\n",
    "                diff=self.diff\n",
    "                for i in range(1,self.m+1):\n",
    "                    for j in range(1,self.n+1):\n",
    "                        diff[i][j] += diff[i][j-1]+diff[i-1][j]-diff[i-1][j-1] \n",
    "                diff = diff[1:-1]\n",
    "                for i, row in enumerate(diff):\n",
    "                    diff[i] = row[1:-1]\n",
    "                return diff\n",
    "        dif=diff2(n,n)\n",
    "        for r1,c1,r2,c2 in queries:\n",
    "            dif.add(r1,c1,r2,c2,1)\n",
    "        return dif.get()\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:\n",
    "        diff = [[0] * (n+1) for _ in range(n+1)]\n",
    "        for r1,c1,r2,c2 in queries:\n",
    "            diff[r1][c1] += 1\n",
    "            diff[r1][c2+1] -= 1\n",
    "            diff[r2+1][c1] -= 1\n",
    "            diff[r2+1][c2+1] += 1\n",
    "        # 直接复用diff作为diff的前缀和数组，可以不开额外空间\n",
    "        for i in range(n):\n",
    "            diff[i+1][0] += diff[i][0]\n",
    "        for j in range(n):\n",
    "            diff[0][j+1] += diff[0][j]\n",
    "        for i in range(1, n):\n",
    "            for j in range(1, n):\n",
    "                diff[i][j] += diff[i][j-1] + diff[i-1][j] - diff[i-1][j-1]\n",
    "        return [x[:-1] for x in diff[:-1]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:\n",
    "        ans=[[0]*n for i in range(n)]\n",
    "        \n",
    "        cha=[[0]*(n+1) for i in range(n+1)]\n",
    "        for q in queries:\n",
    "            x1,y1,x2,y2=q\n",
    "            cha[x1][y1]+=1\n",
    "            cha[x1][y2+1]-=1\n",
    "            cha[x2+1][y1]-=1\n",
    "            cha[x2+1][y2+1]+=1\n",
    "            \n",
    "        ans[0][0]=cha[0][0]\n",
    "        for i in range(1,n):\n",
    "            ans[i][0]=ans[i-1][0]+cha[i][0]\n",
    "        for i in range(1,n):\n",
    "            ans[0][i]=ans[0][i-1]+cha[0][i]\n",
    "        for i in range(1,n):\n",
    "            for j in range(1,n):\n",
    "                ans[i][j]=ans[i-1][j]+ans[i][j-1]+cha[i][j]-ans[i-1][j-1]\n",
    "        \n",
    "        \n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:\n",
    "        arr = [[0]*(n+1) for _ in range(n)]\n",
    "        for a,b,x,y in queries:\n",
    "            for i in range(a,x+1):\n",
    "                arr[i][b] += 1\n",
    "                arr[i][y+1] -= 1\n",
    "        for i in range(n):\n",
    "            t = 0 \n",
    "            for j in range(n+1):\n",
    "                arr[i][j] = arr[i][j]+t\n",
    "                t += arr[i][j]-t\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            ans.append(arr[i][:-1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:\n",
    "        self.new_mat = [[0 for _ in range(n + 2)] for _ in range(n + 2)]\n",
    "        for r1, c1, r2, c2 in queries:\n",
    "            self.new_mat[r1+1][c1+1] += 1\n",
    "            self.new_mat[r1+1][c2+2] -= 1\n",
    "            self.new_mat[r2+2][c1+1] -= 1\n",
    "            self.new_mat[r2+2][c2+2] += 1\n",
    "\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                self.new_mat[i][j] += self.new_mat[i][j - 1] + self.new_mat[i - 1][j] - self.new_mat[i - 1][j - 1]\n",
    "        #print(self.new_mat)\n",
    "        #res = self.new_mat\n",
    "        res = self.new_mat[1:-1]\n",
    "        #print(res)\n",
    "        for i, row in enumerate(res):\n",
    "            res[i] = row[1:-1]\n",
    "        #print(res)\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:\n",
    "        prefix = [[0] * (n + 1) for _ in range(n + 1)]\n",
    "        for i in range(n):\n",
    "            for q in queries:\n",
    "                if i>=q[0] and i<=q[2]:\n",
    "                    prefix[i][q[1]] += 1\n",
    "                    prefix[i][q[3]+1] -= 1\n",
    "        for i in range(0, n):\n",
    "            for k in range(1, n):\n",
    "                prefix[i][k]+=prefix[i][k-1]\n",
    "        return [prefix[i][:n] for i in range(n)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:\n",
    "        mat = [[0] * (n + 2) for _ in range(n + 2)]\n",
    "        for a, b, c, d in queries:\n",
    "            a += 1\n",
    "            b += 1\n",
    "            c += 1\n",
    "            d += 1\n",
    "            mat[a][b] += 1\n",
    "            mat[c + 1][b] -= 1\n",
    "            mat[a][d + 1] -= 1\n",
    "            mat[c + 1][d + 1] += 1\n",
    "        ans = [[0] * n for _ in range(n)]\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                mat[i][j] += mat[i][j - 1] + mat[i - 1][j] - mat[i - 1][j - 1]\n",
    "                ans[i - 1][j - 1] = mat[i][j]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:\n",
    "        N = n+10\n",
    "        b = [[0] * N for _ in range(N)]\n",
    "        c = [[0] * n for _ in range(n)]\n",
    "\n",
    "        def insert(x1, y1, x2, y2, c):\n",
    "            b[x1][y1] += c\n",
    "            b[x2 + 1][y1] -= c\n",
    "            b[x1][y2 + 1] -= c\n",
    "            b[x2 + 1][y2 + 1] += c\n",
    "\n",
    "        for x1, y1, x2, y2 in queries:\n",
    "            insert(x1, y1, x2, y2, 1)\n",
    "\n",
    "        # 通过对差分矩阵求前缀和\n",
    "        for i in range(0, n):\n",
    "            for j in range(0, n):\n",
    "                b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1]\n",
    "                c[i][j] = b[i][j]\n",
    "        return c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:\n",
    "        mat = [[0] * (n+2) for _ in range(n+2)]\n",
    "        for r1, c1, r2, c2 in queries:\n",
    "            mat[r1+1][c1+1] += 1\n",
    "            mat[r1+1][c2+2] -= 1\n",
    "            mat[r2+2][c1+1] -= 1\n",
    "            mat[r2+2][c2+2] += 1\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(1, n+1):\n",
    "                mat[i][j] += mat[i][j-1] + mat[i-1][j] - mat[i-1][j-1]\n",
    "        mat = mat[1:-1]\n",
    "        return [m[1:-1] for m in mat]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:\n",
    "        diff = [[0 for _ in range(n + 1)] for _ in range(n + 1)]\n",
    "        for x in queries:\n",
    "            diff[x[0]][x[1]] += 1\n",
    "            diff[x[0]][x[3] + 1] -= 1\n",
    "            diff[x[2] + 1][x[1]] -= 1\n",
    "            diff[x[2] + 1][x[3] + 1] += 1\n",
    "        for i in range(n):\n",
    "            for j in range(1, n):\n",
    "                diff[i][j] += diff[i][j - 1]\n",
    "        for i in range(1, n):\n",
    "            for j in range(n):\n",
    "                diff[i][j] += diff[i - 1][j]\n",
    "        return [x[:n] for x in diff[:n]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:\n",
    "        delta = [[0]* (n+1) for _ in range(n+1)]\n",
    "        for r1, c1, r2, c2 in queries:\n",
    "            delta[r1][c1]+= 1\n",
    "            delta[r1][c2+1] -= 1\n",
    "            delta[r2+1][c1] -= 1\n",
    "            delta[r2+1][c2+1] += 1\n",
    "        lastRow = [0]*n\n",
    "        res = [[0]*n for _ in range(n)]\n",
    "        for r, (row, dRow) in enumerate(zip(res, delta)):\n",
    "            last = 0\n",
    "            for c, (lv, dv) in enumerate(zip(lastRow, dRow)):\n",
    "                last = row[c] = dv + lv + last - (lastRow[c-1] if c else 0)\n",
    "            lastRow = row\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:\n",
    "        diff = [[0] * (n + 2) for _ in range(n + 2)]\n",
    "        for x1, y1, x2, y2 in queries:\n",
    "            diff[x1 + 1][y1 + 1] += 1\n",
    "            diff[x1 + 1][y2 + 2] -= 1\n",
    "            diff[x2 + 2][y1 + 1] -= 1\n",
    "            diff[x2 + 2][y2 + 2] += 1\n",
    "        \n",
    "        ans = [[0] * n for _ in range(n)]\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                diff[i][j] += diff[i - 1][j] + diff[i][j - 1] - diff[i - 1][j - 1]\n",
    "                ans[i - 1][j - 1] = diff[i][j]\n",
    "    \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:\n",
    "        ans = [[0]*(n + 1) for _ in range(n + 1)]\n",
    "        diff = [[0]*(n + 1) for _ in range(n + 1)]\n",
    "        for x1,y1,x2,y2 in queries:\n",
    "            diff[x1][y1] += 1\n",
    "            diff[x2 + 1][y1] -= 1\n",
    "            diff[x1][y2 + 1] -= 1\n",
    "            diff[x2 + 1][y2 + 1] += 1\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                ans[i + 1][j + 1] = ans[i][j + 1] + ans[i + 1][j] - ans[i][j] + diff[i][j]\n",
    "        \n",
    "        del ans[0]\n",
    "        for x in ans:\n",
    "            del x[0]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:\n",
    "        matrix = [[0] * (n + 2) for _ in range(n + 2)]\n",
    "        mat = []\n",
    "        for x1, y1, x2, y2 in queries:\n",
    "            matrix[x1+1][y1+1] += 1\n",
    "            matrix[x1+1][y2+1+1] -= 1\n",
    "            matrix[x2+1+1][y1+1] -= 1\n",
    "            matrix[x2+1+1][y2+1+1] += 1\n",
    "        for i in range(1, n+1 ,1):\n",
    "            mat.append([])\n",
    "            for j in range(1, n+1 ,1):\n",
    "                matrix[i][j] += matrix[i][j-1]+matrix[i-1][j]-matrix[i-1][j-1]\n",
    "                mat[i-1].append(matrix[i][j])\n",
    "        return mat\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:\n",
    "        diff = [[0] * (n+1) for i in range(n+1)]\n",
    "        for r1, c1, r2, c2 in queries:\n",
    "            diff[r1][c1] += 1\n",
    "            diff[r2+1][c1] -= 1\n",
    "            diff[r1][c2+1] -= 1\n",
    "            diff[r2+1][c2+1] += 1\n",
    "\n",
    "        ans = [[0] * n for i in range(n)]\n",
    "        ans[0][0] = diff[0][0]\n",
    "        for k in range(1,n):\n",
    "            ans[0][k] = ans[0][k-1] + diff[0][k]\n",
    "            ans[k][0] = ans[k-1][0] + diff[k][0]\n",
    "        \n",
    "        for i in range(1, n):\n",
    "            for j in range(1,n):\n",
    "                ans[i][j] = ans[i-1][j] + ans[i][j-1] - ans[i-1][j-1] + diff[i][j]\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:\n",
    "        matrix = [[0] * (n + 2) for _ in range(n + 2)]\n",
    "        mat = []\n",
    "        for x1, y1, x2, y2 in queries:\n",
    "            matrix[x1+1][y1+1] += 1\n",
    "            matrix[x1+1][y2+1+1] -= 1\n",
    "            matrix[x2+1+1][y1+1] -= 1\n",
    "            matrix[x2+1+1][y2+1+1] += 1\n",
    "        for i in range(1, n+1 ,1):\n",
    "            mat.append([])\n",
    "            for j in range(1, n+1 ,1):\n",
    "                matrix[i][j] += matrix[i][j-1]+matrix[i-1][j]-matrix[i-1][j-1]\n",
    "                mat[i-1].append(matrix[i][j])\n",
    "        return mat\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:\n",
    "        diff = [[0]*(n+1) for _ in range(n+1)]\n",
    "        for r1,c1,r2,c2 in queries:\n",
    "            diff[r1][c1] += 1\n",
    "            diff[r2+1][c1] -= 1\n",
    "            diff[r1][c2+1] -= 1\n",
    "            diff[r2+1][c2+1] += 1\n",
    "\n",
    "        res = [[0]*n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(n): \n",
    "                if i==0 and j==0:\n",
    "                    res[0][0] = diff[0][0]\n",
    "                elif i==0:\n",
    "                    res[0][j] = res[0][j-1]+diff[0][j]\n",
    "                elif j==0:\n",
    "                    res[i][0] = res[i-1][0]+diff[i][0]\n",
    "                else:\n",
    "                    res[i][j] = diff[i][j]+res[i-1][j]+res[i][j-1]-res[i-1][j-1]\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:\n",
    "        diff = [[0] * (n + 1) for _ in range(n + 1)]\n",
    "        for r1, c1, r2, c2 in queries:\n",
    "            r2 += 1\n",
    "            c2 += 1\n",
    "            diff[r1][c1] += 1\n",
    "            diff[r1][c2] -= 1\n",
    "            diff[r2][c1] -= 1\n",
    "            diff[r2][c2] += 1\n",
    "        ans = [[0] * (n + 1) for _ in range(n + 1)]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                ans[i + 1][j + 1] = -ans[i][j] + ans[i + 1][j] + ans[i][j + 1] + diff[i][j]\n",
    "        del ans[0]\n",
    "        for r in ans:\n",
    "            del r[0]\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:\n",
    "        diff = [[0 for j in range(n + 2)] for i in range(n + 2)]\n",
    "        for r1, c1, r2, c2 in queries:\n",
    "            diff[r1 + 1][c1 + 1] += 1\n",
    "            diff[r1 + 1][c2 + 2] -= 1\n",
    "            diff[r2 + 2][c1 + 1] -= 1\n",
    "            diff[r2 + 2][c2 + 2] += 1\n",
    "\n",
    "        ret = [[0 for j in range(n)] for i in range(n)]\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                diff[i][j] += diff[i][j - 1] + diff[i - 1][j] - diff[i - 1][j - 1]\n",
    "                ret[i-1][j-1] = diff[i][j]\n",
    "        \n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:\n",
    "        diff = [[0] * (n+2) for i in range(n+2)]\n",
    "        for x1, y1, x2, y2 in queries:\n",
    "            diff[x1+1][y1+1] += 1\n",
    "            diff[x1+1][y2+2] -= 1\n",
    "            diff[x2+2][y1+1] -= 1\n",
    "            diff[x2+2][y2+2] += 1\n",
    "        \n",
    "        # 原地求前缀和\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(1, n+1):\n",
    "                diff[i][j] = diff[i-1][j] + diff[i][j-1] - diff[i-1][j-1] + diff[i][j]\n",
    "        \n",
    "        diff = diff[1:-1]\n",
    "        for i, row in enumerate(diff):\n",
    "            diff[i] = row[1:-1]\n",
    "        return diff"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:\n",
    "        res = [[0]*(n+2) for _ in range(n+2)]\n",
    "        for li, lj, ri, rj in queries:\n",
    "            res[li+1][lj+1] +=1\n",
    "            res[li+1][rj+2] -= 1\n",
    "            res[ri+2][lj+1] -= 1\n",
    "            res[ri+2][rj+2] += 1\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(1, n+1):\n",
    "                res[i][j] += res[i-1][j]-res[i-1][j-1]+res[i][j-1]\n",
    "        res = res[1:-1]\n",
    "        for i in range(len(res)):\n",
    "            res[i] = res[i][1:-1]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:\n",
    "#         mat = [[0 for _ in range(n)] for _ in range(n)]\n",
    "#         for i in range(len(queries)):\n",
    "#             row_1 = queries[i][0]\n",
    "#             col_1 = queries[i][1]\n",
    "#             row_2 = queries[i][2]\n",
    "#             col_2 = queries[i][3]\n",
    "#             for x in range(row_1,row_2+1):\n",
    "#                 for y in range(col_1,col_2+1):\n",
    "#                     mat[x][y] += 1\n",
    "#         return mat \n",
    "\n",
    "class Solution:\n",
    "    def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:\n",
    "        # 二维差分矩阵初始化\n",
    "        diff = [[0] * (n + 2) for _ in range(n + 2)]\n",
    "        # 标记需要更改的区域（体现在之后的二维前缀和中）\n",
    "        for query in queries:\n",
    "            row1, col1, row2, col2 = query\n",
    "            diff[row1 + 1][col1 + 1] += 1\n",
    "            diff[row1 + 1][col2 + 2] -= 1\n",
    "            diff[row2 + 2][col1 + 1] -= 1\n",
    "            diff[row2 + 2][col2 + 2] += 1\n",
    "        # 计算diff二维前缀和\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                diff[i][j] = diff[i][j] + diff[i][j - 1] + diff[i - 1][j] - diff[i - 1][j - 1]\n",
    "        # 中间 n*n 的部分\n",
    "        diff = diff[1:-1]\n",
    "        for i, row in enumerate(diff):\n",
    "            diff[i] = row[1:-1]\n",
    "        return diff\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:\n",
    "\n",
    "        ans = [[0 for i in range(n)] for j in range(n)]\n",
    "        for query in queries:\n",
    "            ans[query[0]][query[1]]+=1\n",
    "            if query[2]+1<n:\n",
    "                ans[query[2]+1][query[1]]-=1\n",
    "            if query[3]+1<n :\n",
    "                ans[query[0]][query[3]+1]-=1 \n",
    "            if query[2]+1<n and query[3]+1<n :\n",
    "                ans[query[2]+1][query[3]+1]+=1\n",
    "        dp = ans.copy() \n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if i==0 and j==0:\n",
    "                    pass \n",
    "                elif i==0:\n",
    "                    dp[i][j] = dp[i][j-1]+ans[i][j] \n",
    "                elif j==0:\n",
    "                    dp[i][j] = dp[i-1][j]+ans[i][j] \n",
    "                else:\n",
    "                    dp[i][j] = dp[i-1][j]+dp[i][j-1]+ans[i][j]-dp[i-1][j-1] \n",
    "        return dp   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:\n",
    "        \n",
    "        def update(x, y, d):\n",
    "            while x <= n:\n",
    "                tmp = y\n",
    "                while tmp <= n:\n",
    "                    h[x][tmp] += d\n",
    "                    tmp += tmp & -tmp\n",
    "                x += x & -x\n",
    "        def query(x, y):\n",
    "            s = 0\n",
    "            while x > 0:\n",
    "                tmp = y\n",
    "                while tmp > 0:\n",
    "                    s += h[x][tmp]\n",
    "                    tmp -= tmp & -tmp\n",
    "                x -= x & -x\n",
    "            return s\n",
    "        \n",
    "        h = [[0] * (n + 1) for _ in range(n + 1)]\n",
    "        for x1, y1, x2, y2 in queries:\n",
    "            x1 += 1; y1 += 1; x2 += 1; y2 += 1\n",
    "            update(x1, y1, 1)\n",
    "            update(x1, y2 + 1, -1)\n",
    "            update(x2 + 1, y1, -1)\n",
    "            update(x2 + 1, y2 + 1, 1)\n",
    "            \n",
    "        ret = [[0] * n for _ in range(n)]\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                ret[i - 1][j - 1] = query(i, j)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:\n",
    "        # 二维差分模板\n",
    "        diff = [[0 for _ in range(n+1)] for _ in range(n+1)]\n",
    "        for r1, c1, r2, c2 in queries:\n",
    "            diff[r1][c1] += 1\n",
    "            diff[r1][c2 + 1] -= 1\n",
    "            diff[r2 + 1][c1] -= 1\n",
    "            diff[r2 + 1][c2 + 1] += 1\n",
    "\n",
    "        print(diff)\n",
    "        # 用二维前缀和复原（原地修改）\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if i == 0 and j == 0: continue\n",
    "                if i == 0:\n",
    "                    diff[i][j] += diff[i][j - 1]\n",
    "                elif j == 0:\n",
    "                    diff[i][j] += diff[i - 1][j]\n",
    "                else:\n",
    "                    diff[i][j] += diff[i][j - 1] + diff[i - 1][j] - diff[i - 1][j - 1]\n",
    "        \n",
    "        return [dp[:n] for dp in diff[:n]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:\n",
    "        diff = [[0] * (n + 1) for _ in range(n + 1)]\n",
    "        for r1, c1, r2, c2 in queries:\n",
    "            diff[r1][c1] += 1\n",
    "            diff[r1][c2 + 1] -= 1\n",
    "            diff[r2 + 1][c1] -= 1\n",
    "            diff[r2 + 1][c2 + 1] += 1\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(1, n):\n",
    "                diff[i][j] += diff[i][j - 1]\n",
    "        for j in range(n):\n",
    "            for i in range(1, n):\n",
    "                diff[i][j] += diff[i - 1][j]\n",
    "        \n",
    "        return [x[:n] for x in diff[:n]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:\n",
    "        rowdiffs = [[0] * (n + 1) for _ in range(n)]\n",
    "        for q in queries:\n",
    "            for r in range(q[0], q[2] + 1):\n",
    "                rowdiffs[r][q[1]] += 1\n",
    "                if q[3] + 1 < n:\n",
    "                    rowdiffs[r][q[3] + 1] -= 1\n",
    "        res = [[0] * n for _ in range(n)]          \n",
    "        for i in range(n):\n",
    "            cur = 0\n",
    "            for j in range(n):\n",
    "                cur += rowdiffs[i][j]\n",
    "                res[i][j] = cur\n",
    "        return res                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:\n",
    "        res = [[0] * n for _ in range(n)]\n",
    "        diff = [[0] * n for _ in range(n)]\n",
    "        for x1, y1, x2, y2 in queries:\n",
    "            for i in range(x1, x2 + 1):\n",
    "                diff[i][y1] += 1\n",
    "                if y2 < n - 1:\n",
    "                    diff[i][y2 + 1] -= 1\n",
    "        # print(diff)\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                res[i][j] = diff[i][j]\n",
    "                if j:\n",
    "                    res[i][j] += res[i][j - 1]\n",
    "                    \n",
    "        return res\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:\n",
    "        diff = [[0] * (n + 1) for _ in range(n + 1)]\n",
    "        for x1, y1, x2, y2 in queries:\n",
    "            diff[x1][y1] += 1\n",
    "            diff[x1][y2 + 1] -= 1\n",
    "            diff[x2 + 1][y1] -= 1\n",
    "            diff[x2 + 1][y2 + 1] += 1\n",
    "        \n",
    "        # print(diff)\n",
    "        # print(diff[:-1])\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if i:\n",
    "                    diff[i][j] += diff[i - 1][j]\n",
    "                if j:\n",
    "                    diff[i][j] += diff[i][j - 1]\n",
    "                if i and j:\n",
    "                    diff[i][j] -= diff[i - 1][j - 1]\n",
    "        \n",
    "        return [diff[x][:-1] for x in range(n)]\n",
    "            \n",
    "        \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import *\n",
    "\n",
    "class Solution:\n",
    "    def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:\n",
    "        queries.sort(key = lambda x: x[1])\n",
    "        res = [[] for _ in range(n)]\n",
    "        print(queries)\n",
    "        for i in range(n):\n",
    "            heap, pres = [], 0\n",
    "            for j in range(n):\n",
    "                while heap and heap[0] < j:\n",
    "                    heappop(heap)\n",
    "                while pres < len(queries) and j == queries[pres][1]:\n",
    "                    if queries[pres][0] <= i <= queries[pres][2]:\n",
    "                        heappush(heap, queries[pres][3])\n",
    "                    pres += 1\n",
    "                res[i].append(len(heap))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:\n",
    "        ans=[[0]*n for i in range(n)]\n",
    "        #  由一维过程，仿照到二维上，将二维化为n个一维问题去解决\n",
    "        # 一维过程为 [x1,x2] 记录到counter 上，计算过程为x[i]=x[i-1]+x2[i]-x1[i],非x[i]=min(x1[i],x2[i] 原因在于[1,2],[4,5]时x[3]的值)\n",
    "        # queries.sort()\n",
    "        # for query in queries:\n",
    "        #     x1=query[0]\n",
    "        #     x2=query[2]\n",
    "        #     y1=query[1]\n",
    "        #     y2=query[3]\n",
    "        #     for x in range(x1,x2+1):\n",
    "        #         for y in range(y1,y2+1):\n",
    "        #             ans[x][y]+=1\n",
    "        xx1=[[0]*n for i in range(n)]\n",
    "        xx2=[[0]*n for i in range(n)]\n",
    "        xx=[[0]*n for i in range(n)]\n",
    "        # yy1=[[0]*n for i in range(n)]\n",
    "        # yy2=[[0]*n for i in range(n)]\n",
    "        for query in queries:\n",
    "            x1=query[0]\n",
    "            x2=query[2]\n",
    "            y1=query[1]\n",
    "            y2=query[3]\n",
    "            # for x in range(x1,x2+1):\n",
    "            #     yy1[x][y1]+=1\n",
    "            #     yy2[x][y2]+=1\n",
    "            for y in range(y1,y2+1):\n",
    "                xx1[y][x1]+=1\n",
    "                xx2[y][x2]+=1\n",
    "        # 第y列的行数为xx1--xx2\n",
    "        # for j in range(0,n):\n",
    "        #     for i in range(1,n):\n",
    "        #         xx1[j][i]+=xx1[j][i-1]\n",
    "                # yy1[j][i]+=y1[i-1]\n",
    "        # for j in range(0,n):\n",
    "        #     for i in range(n-2,-1,-1):\n",
    "        #         xx2[j][i]+=xx2[j][i+1]\n",
    "                # yy2[j][i]+=yy2[i+1]\n",
    "        for j in range(0,n):\n",
    "            xx[j][0]=xx1[j][0]\n",
    "            for i in range(1,n):\n",
    "                xx[j][i]=xx[j][i-1]+xx1[j][i]-xx2[j][i-1]\n",
    "        # print(x1,x2,y1,y2)\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                # ans[i][j]=min(x1[i],x2[i],y1[j],y2[j])\n",
    "                # ans[i][j]=min(xx1[j][i],xx2[j][i])\n",
    "                ans[i][j]=xx[j][i]\n",
    "\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:\n",
    "        res = [[0] * (n + 2) for _ in range(n + 2)]\n",
    "        ans = [[0] * n for _ in range(n)]\n",
    "        #二维差分模版\n",
    "        for row1, col1, row2, col2 in queries:\n",
    "            res[row1 + 1][col1 + 1] += 1\n",
    "            res[row1 + 1][col2 + 2] -= 1\n",
    "            res[row2 + 2][col1 + 1] -= 1\n",
    "            res[row2 + 2][col2 + 2] += 1\n",
    "        #用二维前缀和恢复\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(1, n+1):\n",
    "                res[i][j] += res[i][j - 1] + res[i-1][j] - res[i - 1][j - 1]\n",
    "        print(res)\n",
    "        for i in range(0,n):\n",
    "            for j in range(0, n):\n",
    "                ans[i][j] = res[i + 1][j + 1]\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:\n",
    "        ans=[[0]*n for i in range(n)]\n",
    "        queries.sort()\n",
    "        # for query in queries:\n",
    "        #     x1=query[0]\n",
    "        #     x2=query[2]\n",
    "        #     y1=query[1]\n",
    "        #     y2=query[3]\n",
    "        #     for x in range(x1,x2+1):\n",
    "        #         for y in range(y1,y2+1):\n",
    "        #             ans[x][y]+=1\n",
    "        xx1=[[0]*n for i in range(n)]\n",
    "        xx2=[[0]*n for i in range(n)]\n",
    "        xx=[[0]*n for i in range(n)]\n",
    "        # yy1=[[0]*n for i in range(n)]\n",
    "        # yy2=[[0]*n for i in range(n)]\n",
    "        for query in queries:\n",
    "            x1=query[0]\n",
    "            x2=query[2]\n",
    "            y1=query[1]\n",
    "            y2=query[3]\n",
    "            # for x in range(x1,x2+1):\n",
    "            #     yy1[x][y1]+=1\n",
    "            #     yy2[x][y2]+=1\n",
    "            for y in range(y1,y2+1):\n",
    "                xx1[y][x1]+=1\n",
    "                xx2[y][x2]+=1\n",
    "        # 第y列的行数为xx1--xx2\n",
    "        # for j in range(0,n):\n",
    "        #     for i in range(1,n):\n",
    "        #         xx1[j][i]+=xx1[j][i-1]\n",
    "                # yy1[j][i]+=y1[i-1]\n",
    "        # for j in range(0,n):\n",
    "        #     for i in range(n-2,-1,-1):\n",
    "        #         xx2[j][i]+=xx2[j][i+1]\n",
    "                # yy2[j][i]+=yy2[i+1]\n",
    "        for j in range(0,n):\n",
    "            xx[j][0]=xx1[j][0]\n",
    "            for i in range(1,n):\n",
    "                xx[j][i]=xx[j][i-1]+xx1[j][i]-xx2[j][i-1]\n",
    "        # print(x1,x2,y1,y2)\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                # ans[i][j]=min(x1[i],x2[i],y1[j],y2[j])\n",
    "                # ans[i][j]=min(xx1[j][i],xx2[j][i])\n",
    "                ans[i][j]=xx[j][i]\n",
    "\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:\n",
    "        ans=[[0]*n for i in range(n)]\n",
    "        queries.sort()\n",
    "        # for query in queries:\n",
    "        #     x1=query[0]\n",
    "        #     x2=query[2]\n",
    "        #     y1=query[1]\n",
    "        #     y2=query[3]\n",
    "        #     for x in range(x1,x2+1):\n",
    "        #         for y in range(y1,y2+1):\n",
    "        #             ans[x][y]+=1\n",
    "        xx1=[[0]*n for i in range(n)]\n",
    "        xx2=[[0]*n for i in range(n)]\n",
    "        xx=[[0]*n for i in range(n)]\n",
    "        # yy1=[[0]*n for i in range(n)]\n",
    "        # yy2=[[0]*n for i in range(n)]\n",
    "        for query in queries:\n",
    "            x1=query[0]\n",
    "            x2=query[2]\n",
    "            y1=query[1]\n",
    "            y2=query[3]\n",
    "            # for x in range(x1,x2+1):\n",
    "            #     yy1[x][y1]+=1\n",
    "            #     yy2[x][y2]+=1\n",
    "            for y in range(y1,y2+1):\n",
    "                xx1[y][x1]+=1\n",
    "                xx2[y][x2]+=1\n",
    "        # 第y列的行数为xx1--xx2\n",
    "        # for j in range(0,n):\n",
    "        #     for i in range(1,n):\n",
    "        #         xx1[j][i]+=xx1[j][i-1]\n",
    "                # yy1[j][i]+=y1[i-1]\n",
    "        # for j in range(0,n):\n",
    "        #     for i in range(n-2,-1,-1):\n",
    "        #         xx2[j][i]+=xx2[j][i+1]\n",
    "                # yy2[j][i]+=yy2[i+1]\n",
    "        for j in range(0,n):\n",
    "            xx[j][0]=xx1[j][0]\n",
    "            for i in range(1,n):\n",
    "                xx[j][i]=xx[j][i-1]+xx1[j][i]-xx2[j][i-1]\n",
    "        # print(x1,x2,y1,y2)\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                # ans[i][j]=min(x1[i],x2[i],y1[j],y2[j])\n",
    "                # ans[i][j]=min(xx1[j][i],xx2[j][i])\n",
    "                ans[i][j]=xx[j][i]\n",
    "\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:\n",
    "        ans=[[0]*n for i in range(n)]\n",
    "        #  由一维过程，仿照到二维上，将二维化为n个一维问题去解决\n",
    "        queries.sort()\n",
    "        # for query in queries:\n",
    "        #     x1=query[0]\n",
    "        #     x2=query[2]\n",
    "        #     y1=query[1]\n",
    "        #     y2=query[3]\n",
    "        #     for x in range(x1,x2+1):\n",
    "        #         for y in range(y1,y2+1):\n",
    "        #             ans[x][y]+=1\n",
    "        xx1=[[0]*n for i in range(n)]\n",
    "        xx2=[[0]*n for i in range(n)]\n",
    "        xx=[[0]*n for i in range(n)]\n",
    "        # yy1=[[0]*n for i in range(n)]\n",
    "        # yy2=[[0]*n for i in range(n)]\n",
    "        for query in queries:\n",
    "            x1=query[0]\n",
    "            x2=query[2]\n",
    "            y1=query[1]\n",
    "            y2=query[3]\n",
    "            # for x in range(x1,x2+1):\n",
    "            #     yy1[x][y1]+=1\n",
    "            #     yy2[x][y2]+=1\n",
    "            for y in range(y1,y2+1):\n",
    "                xx1[y][x1]+=1\n",
    "                xx2[y][x2]+=1\n",
    "        # 第y列的行数为xx1--xx2\n",
    "        # for j in range(0,n):\n",
    "        #     for i in range(1,n):\n",
    "        #         xx1[j][i]+=xx1[j][i-1]\n",
    "                # yy1[j][i]+=y1[i-1]\n",
    "        # for j in range(0,n):\n",
    "        #     for i in range(n-2,-1,-1):\n",
    "        #         xx2[j][i]+=xx2[j][i+1]\n",
    "                # yy2[j][i]+=yy2[i+1]\n",
    "        for j in range(0,n):\n",
    "            xx[j][0]=xx1[j][0]\n",
    "            for i in range(1,n):\n",
    "                xx[j][i]=xx[j][i-1]+xx1[j][i]-xx2[j][i-1]\n",
    "        # print(x1,x2,y1,y2)\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                # ans[i][j]=min(x1[i],x2[i],y1[j],y2[j])\n",
    "                # ans[i][j]=min(xx1[j][i],xx2[j][i])\n",
    "                ans[i][j]=xx[j][i]\n",
    "\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:\n",
    "        ans = [[0]*n for _ in range(n)]\n",
    "        diff = [[0]*(n + 2) for _ in range(n + 2)]\n",
    "        for x1,y1,x2,y2 in queries:\n",
    "            x1 += 1\n",
    "            y1 += 1\n",
    "            x2 += 1\n",
    "            y2 += 1\n",
    "            diff[x1][y1] += 1\n",
    "            diff[x2 + 1][y1] -= 1\n",
    "            diff[x1][y2 + 1] -= 1\n",
    "            diff[x2 + 1][y2 + 1] += 1\n",
    "        \n",
    "        for i in range(1,n + 1):\n",
    "            for j in range(1,n + 1):\n",
    "                diff[i][j] += diff[i - 1][j] + diff[i][j - 1] - diff[i - 1][j - 1]\n",
    "                ans[i - 1][j - 1] += diff[i][j]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:\n",
    "        # 二维差分模板\n",
    "        diff = [[0] * (n + 2) for _ in range(n + 2)]\n",
    "        ans = [[0]*n for _ in range(n)]\n",
    "        for r1, c1, r2, c2 in queries:\n",
    "            diff[r1 + 1][c1 + 1] += 1\n",
    "            diff[r1 + 1][c2 + 2] -= 1\n",
    "            diff[r2 + 2][c1 + 1] -= 1\n",
    "            diff[r2 + 2][c2 + 2] += 1\n",
    "\n",
    "        # 用二维前缀和复原（原地修改）\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                diff[i][j] += diff[i][j - 1] + diff[i - 1][j] - diff[i - 1][j - 1]\n",
    "                ans[i - 1][j - 1] += diff[i][j]\n",
    "        # 保留中间 n*n 的部分，即为答案\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:\n",
    "        # 二维差分模板\n",
    "        diff = [[0] * (n + 2) for _ in range(n + 2)]\n",
    "        ans = [[0]*(n + 1) for _ in range(n + 1)]\n",
    "        for r1, c1, r2, c2 in queries:\n",
    "            diff[r1 + 1][c1 + 1] += 1\n",
    "            diff[r1 + 1][c2 + 2] -= 1\n",
    "            diff[r2 + 2][c1 + 1] -= 1\n",
    "            diff[r2 + 2][c2 + 2] += 1\n",
    "\n",
    "        # 用二维前缀和复原（原地修改）\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                diff[i][j] += diff[i][j - 1] + diff[i - 1][j] - diff[i - 1][j - 1]\n",
    "                ans[i][j] += diff[i][j]\n",
    "        # 保留中间 n*n 的部分，即为答案\n",
    "        del ans[0]\n",
    "        for row in ans:\n",
    "            del row[0]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:\n",
    "        res = np.zeros((n,n),np.int16)\n",
    "        for q1,q2,q3,q4 in queries:\n",
    "            res[q1:q3+1,q2:q4+1] += 1\n",
    "        return res.tolist()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:\n",
    "        res = np.zeros((n,n),np.int16)\n",
    "        for q1,q2,q3,q4 in queries:\n",
    "            res[q1:q3+1,q2:q4+1] += 1\n",
    "        return res.tolist()"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
